package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 找到初始输入字符串 II
 */

public class Code3333 {
    public static void main(String[] args) {
        String word = "aabbccdd";
        int k = 7;
        System.out.println(new Code3333().possibleStringCount(word, k));
    }

    public int possibleStringCount(String word, int k) {
        int n = word.length();
        if (n < k) { // 无法满足要求
            return 0;
        }

        final int MOD = 1_000_000_007;
        List<Integer> cnts = new ArrayList<>();
        long ans = 1;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt++;
            if (i == n - 1 || word.charAt(i) != word.charAt(i + 1)) {
                // 如果 cnt = 1，这组字符串必选，无需参与计算
                if (cnt > 1) {
                    if (k > 0) {
                        cnts.add(cnt - 1);
                    }
                    ans = ans * cnt % MOD;
                }
                k--; // 注意这里把 k 减小了
                cnt = 0;
            }
        }

        if (k <= 0) {
            return (int) ans;
        }

        int m = cnts.size();
        int[][] f = new int[m + 1][k];
        Arrays.fill(f[0], 1);
        int[] s = new int[k + 1];
        for (int i = 0; i < m; i++) {
            // 计算 f[i] 的前缀和数组 s
            for (int j = 0; j < k; j++) {
                s[j + 1] = (s[j] + f[i][j]) % MOD;
            }
            int c = cnts.get(i);
            // 计算子数组和
            for (int j = 0; j < k; j++) {
                f[i + 1][j] = (s[j + 1] - s[Math.max(j - c, 0)]) % MOD;
            }
        }

        return (int) ((ans - f[m][k - 1] + MOD) % MOD); // 保证结果非负
    }
}
